import java.io.FileReader; // used to read a file
import java.io.PrintWriter; // used to write to a file
import java.util.ArrayList; //used to store lines and points of convex hull
import java.util.Iterator; // used to traverse ArrayList
import java.util.Scanner;  //used to read the integers from input file
import javax.swing.JOptionPane; //used to create dialog boxes to get filenames

/**
 * @author Pedro J Toro
 * @CSC8050 Design and Analysis of Algorithms
 * 
 * This program reads in an input file that contains a list of numbers; each line 
 * in the file represents a set of points. After reading a line, the program calculates
 * the set of points that will form a convex hull (if possible) from those points and
 * display then as output and to an output file. 
 */
public class ConvexHull {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// declare variables
		String inFileName, outFileName; // user provided path and filenames.
		Scanner inFile; // handle to the input file
		PrintWriter outFile; // handle to the output file
		
		// prompt user for input file name and location and store it in
		//inFileName = "C:\\Projects\\csc8050\\src\\points.txt";
		inFileName = JOptionPane.showInputDialog(null, "Please enter input filename and location as a path");

		if (inFileName == null) { // this means user pressed cancel on the
			// dialog box
			System.out.println("no input file found");
			System.exit(0);
		}

		// prompt user for output file name and location and store it in
		//outFileName = "C:\\Projects\\csc8050\\src\\hulls.txt";
		outFileName = JOptionPane.showInputDialog(null, "Please enter output filename and location as a path");
		
		if (outFileName == null) { // this means user pressed cancel on the
			// dialog box
			System.out.println("no output file found");
			System.exit(0);
		}

		try {
			// Create the inFile to read and outFile to write
			inFile = new Scanner(new FileReader(inFileName));
			outFile = new PrintWriter(outFileName);

			double x, y;
			int pointCount; // number of points read in from one line from the input file

			ArrayList<Point> myPoints = new ArrayList<Point>(); // points from one line from the input file
			ArrayList<Line> myConvexHull = new ArrayList<Line>(); // edges of convex hull
			String[] myNumbers; // numbers read in from one line from the input file
			Line myLine; // temporary line for checking if convex hull edge

			boolean previous, current; // used for checking if all points are under the line
			boolean first; // used for checking if it is the first point checked against the line
			
			while (inFile.hasNextLine()) {
				// get line of numbers and place into array of type double
				myNumbers = inFile.nextLine().split(" ");

				// initialize point count
				pointCount = 0;

				try {
					// place numbers into Point ArrayList
					while (pointCount < myNumbers.length / 2) {
						x = Double.parseDouble(myNumbers[2 * pointCount]);
						y = Double.parseDouble(myNumbers[2 * pointCount + 1]);
						
						myPoints.add(new Point(x, y)); // add point to ArrayList
						pointCount++; // increment point count
					}
					
					// check all possible pairs of point if they form an edge of the convex hull
					for (int i = 0; i < pointCount - 1; i++) {
						for (int j = i + 1; j < pointCount; j++) {
							// create a line using two points i and j from ArrayList
							myLine = new Line(new Point(myPoints.get(i).getX(), myPoints.get(i).getY()),
												new Point(myPoints.get(j).getX(), myPoints.get(j).getY()));

							// initialize variables 
							previous = current = false;
							first = true;
							
							// traverse all points
							for (int k = 0; k < pointCount; k++) {
								// do not do anything with points already in line
								
								if (!(myLine.getP().equals(myPoints.get(k))
										|| myLine.getQ().equals(myPoints.get(k)))) {

									// is point under the line?
									switch (myLine.isUnder(myPoints.get(k))) {
										case 1:
											current = true;
											break;
										case 0:
											current = false;
											break;
										case -1:
											current = previous;
											break;
									}
									
									
									if ((current != previous) && !(first)) {
										// line is not an edge of the convex hull
										break;
									}

									previous = current; 
									first = false; // point is no longer the first point checked against
								}
							}

							if (current == previous) {
								// line is an edge of the convex hull
								if (!myConvexHull.contains(myLine)) {
									myConvexHull.add(myLine);	
								}								
							}
						}
					}

					// extract vertices in order along the polygon
					ArrayList<Point> myVertices;
					myVertices = extractVertices(myConvexHull);

		 			// display summary of convex hull points
		 			printVerticesSummary(myVertices, outFile);
				}catch (NumberFormatException e) {
					// non numeric data input, error
					System.out.println("Invalid Input Data");
					outFile.println("Invalid Input Data");
				}
					 			
				// clear the ArrayList for the next set of points
				myPoints.clear();
				myConvexHull.clear();
			}
			
			// close both input and output files
			inFile.close();
			outFile.close();
		} catch (Exception e) {
			// problem with input/output file, error
			System.out.println("Problem with input or output file.");
			System.exit(1);
		}
	}
	
	/**
	 * Extract vertices from ArrayList of Lines that form convex hull.
	 * @param lines ArayList of Line that form convex hull
	 * @return ArrayList of Point that form convex hull
	 */
	private static ArrayList<Point> extractVertices(ArrayList<Line> lines) {
		ArrayList<Point> vertices = new ArrayList<Point>(); // store vertices of convex hull
		Point tempPoint; // temporary point
		Point point1; // 1st point in the line
		Point point2; // 2nd point in the line
		int index; // used for holding the position of 
		
		boolean startAtP; // start at the 1st point of the line?
		
		index = 0; // initialize index
		if (lines.size() == 1) {
			// only two points exist
			vertices.add(lines.get(index).getP());
			vertices.add(lines.get(index).getQ());
		} else {
			startAtP = true; // initialize startAtP to start at the 1st point in line
			
			while (!lines.isEmpty()) {
				// get point values from line
				point1 = lines.get(index).getP();
				point2 = lines.get(index).getQ();

				if (startAtP) {
					// add 1st point to ArrayList and search for 2nd point in other lines
					vertices.add(point1);
					tempPoint = point2;
				} else {
					// add 2nd point to ArrayList and search for 1st point in other lines
					vertices.add(point2);
					tempPoint = point1;
				}

				// remove current line from ArrayList of lines, no longer needed
				lines.remove(lines.get(index));

				index = 0; // initialize index and try to find point in ArrayList of lines
				while (!lines.isEmpty() && (index < lines.size()) && !(lines.get(index).hasPoint(tempPoint))) {
					index++;
				}

				if (!lines.isEmpty() && lines.get(index).hasPoint(tempPoint)) {
					// found point in ArrayList of lines
					if (lines.get(index).getP().equals(tempPoint)) {
						// point was found in the 1st point in the line
						startAtP = true;					
					} else {
						// point was found in the 2nd point in the line
						startAtP = false;
					}
				}		
			}
		}	
		
		return vertices;
	}

	/**
	 * Displays list of points that form convex hull.
	 * @param vertices, ArrayList of Point that forms convex hull
	 */
	private static void printVerticesSummary(ArrayList<Point> vertices) {
		Iterator<Point> iter = vertices.iterator();
		while (iter.hasNext()) {
			System.out.printf("%-16s", iter.next().toString());
		}
		
		// goto newline
		System.out.println();
	}
	
	/**
	 * Displays list of points that form convex hull and writes it to a file.
	 * @param vertices, ArrayList of Point that forms convex hull
	 */
	private static void printVerticesSummary(ArrayList<Point> vertices, PrintWriter outFile) {
		Iterator<Point> iter = vertices.iterator();
		Point myPoint;
		
		while (iter.hasNext()) {
			myPoint = iter.next();
			
			System.out.printf("%-16s", myPoint.toString());
			outFile.printf("%-16s", myPoint.toString());
		}
		
		// goto newline
		System.out.println();
		outFile.println();
	}

}